---
sidebar_position: 2
---

# Пузырьковая сортировка

:::info

Основано на статьях ["Сортировка пузырьком"](https://ru.wikipedia.org/wiki/Сортировка_пузырьком), ["Bubble Sort Algorithm"](https://www.geeksforgeeks.org/bubble-sort/), ["Пузырьковая сортировка и все-все-все"](https://habr.com/ru/post/204600/) и ["Общие сведения об алгоритмах сортировки"](https://www.evkova.org/kursovye-raboty/obschie-svedeniya-ob-algoritmah-sortirovki).

:::

**Сортировка простыми обменами**, **сортировка пузырьком** (англ. *bubble sort*) — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: $O(n^2)$.

## Алгоритм

Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется перестановка элементов. Проходы по массиву повторяются $N-1$ раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим "наибольшим элементом", а наименьший элемент перемещается на одну позицию к началу массива ("всплывает" до нужной позиции, как пузырёк в воде — отсюда и название алгоритма).

## Пример работы

При пузырьковой сортировке сравниваются соседние элементы и меняются местами, если следующий элемент меньше предыдущего. Требуется несколько проходов по данным. Во время первого прохода сравниваются первые два элемента в массиве. Если они не в порядке, они меняются местами и затем сравнивается элементы в следующей паре. При том же условии они так же меняются местами. Таким образом сортировка происходит в каждом цикле пока не будет достигнут конец массива).

![Пример работы пузырьковой сортировки](images/bubble-sort-example.png)
